package com.ygu.Enter1;

/**
 * 链表的插入 ①头部插入:我们只要链表的投节点是不存在节点的 因此我们把需要插入的节点
 * 的指针域指向投节点的地址即可。
 * ②尾部添加:我们只需要将我们的要在尾部添加的节点指向我们所定义的哨兵tail节点的地址即可
 * @param <E>
 */

public class myLinkedList<E>{

    //为我们所设计的哨兵头节点
    private final Node<E> head;
    //为我们所设计的哨兵尾节点
    private final Node<E> tail;
    private int size;

    public myLinkedList(Node<E> head, Node<E> tail) {
        this.head = head;
        this.tail = tail;
    }

    // 构造函数初始化头尾节点
    public myLinkedList() {
//其实这两个节点可以看成两个 哨兵节点(虚拟的节点)
        this.head = new Node<>(null);
        this.tail = new Node<>(null);
        head.next = tail;
        this.size = 0;
    }


    public void addFirst(E e){
        Node<E> newNode = new Node<>(e);
        Node<E> temp = head.next;

        newNode.next = temp;
        head.next = newNode;

        size++;
    }

    public void addList(E e){
        Node<E> newNode = new Node<>(e);
        Node<E> temp = new Node<>();

        if(size-1 > 0){
            //找到尾节点
            temp = getNode(size-1);
        }else {
            temp = head;
        }

        //将newNode设为尾节点
        newNode.next = tail;
        //将原本的尾节点地址指向新的尾节点
        temp.next = newNode;
    }

    /**
     * 添加指定位置的节点
     * @param index 索引
     * @param element Node
     */
    public void add(int index, E element) {
        //创建节点
        Node<E> node = new Node<>(element);
        //先找到要插入节点的位置
        Node<E> perNode = getNode(index);
        Node<E> temp;

        if(size-1>0){
            //获得到目标节点的上一个节点  或者拿到目标节点的下一个节点
            temp = getNode(index-1);
        }else {
            temp = head;
        }

        node.next = perNode;
        temp.next = node;

        size++;
    }


    /**
     * 删除头节点  就是把该节点置为null
     * @return 节点数据
     */
    public E removeFirst() {
        //先原本的头节点找出
        Node<E> x = head.next;
        //只需要将我们的哨兵节点指向 下下一个节点即可
        head.next = head.next.next;
        x = null;
        size--;

        return x.val;
    }

    /**
     * 删除尾节点
     * @return 节点信息
     */
    public E removeLast() {
        //原本的尾节点
        Node<E> x = getNode(size-1);
        Node<E> temp ;
        if(size-2>0){
            //最后一个节点的上一个节点
            temp = getNode(size-2);
        }else {
            temp = head;
        }

        temp.next = tail;
        //将原本的node 的指针域变为null
        x.next = null;

        return x.val;
    }

    /**
     * 删除对应index 的节点
     * @param index 索引
     * @return 节点信息
     */
    public E remove(int index) {
        Node<E> node = getNode(index);
        Node<E> perv;

        if(size-1>0){
            perv = getNode(index-1);
        }else {
            perv = head;
        }
        perv.next = node.next;
        node.next = null;

        return perv.val;
    }

    /**
     * 获取头节点
     * @return 信息
     */
    public E getFirst() {
        return head.next.val;
    }

    public E getLast() {
        //获取到尾节点
        return getNode(size - 1).val;
    }

    /**
     * 获取指定节点
     * @param index 索引
     * @return 信息
     */
    public E get(int index) {
        return getNode(index).val;
    }

    /***** 改 *****/

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> p = getNode(index);

        E oldVal = p.val;
        p.val = element;

        return oldVal;
    }

    /***** 其他工具函数 *****/
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    /**
     * 检查 index 索引位置是否可以存在元素
     */
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    /**
     * 检查 index 索引位置是否可以添加元素
     */
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    // 返回 index 对应的 Node
    // 注意：请保证传入的 index 是合法的
    private Node<E> getNode(int index) {
        //p为头节点  因为head是我们上面所设计的哨兵头结点
        Node<E> p = head.next;

        //通过遍历指针来进行找到对应需要的Node
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

}
